from copy import deepcopy

from utils.log import Log
from utils.profile import Profile
from utils.generator import Generator


# 2024/05/28 以色列正式进入倒计时
# 2024/05/29 DMI 5.0的热效比能达到恐怖的46.06%,无论插混还是增程都能轻松上2000公里

class Radix(Log):
    # n_bits 是base的位数,尽量用位运算
    def __init__(self, arr, n_bits=4):
        super(Radix, self).__init__()
        self.arr = arr
        self.arr_backup = deepcopy(self.arr)
        self.n_bits = n_bits
        self.base_bits = (1 << self.n_bits) - 1
        self.cnts = [0] * (1 << self.n_bits)

    @Profile(log=True)
    def get_width(self, val):
        width = 0
        while (self.base_bits & val) or (val >> self.n_bits):
            val >>= self.n_bits
            width += 1
        return width

    def _reset_something(self):
        for i in range(len(self.cnts)):
            self.cnts[i] = 0
        # for i in range(len(self.arr_backup)):
        #     self.arr_backup[i] = 0

    @Profile(log=True)
    def sort(self):
        # ref: https://www.bilibili.com/video/BV1Lh4y1c7Aw/?spm_id_from=333.788.recommend_more_video.-1&vd_source=ad559e41b561d48861f70d0187e51e02
        # 实现部分没有用他的方法
        n_width = 0
        for v in self.arr:
            n_width = max(n_width, self.get_width(v))
        for i in range(n_width):
            self._reset_something()
            for v in self.arr:
                index = (v >> (self.n_bits * i)) & self.base_bits
                self.cnts[index] += 1
            for j in range(1, 1 << self.n_bits):
                self.cnts[j] += self.cnts[j - 1]
            for v in reversed(self.arr):
                index = (v >> (self.n_bits * i)) & self.base_bits
                self.cnts[index] -= 1
                self.arr_backup[self.cnts[index]] = v
            self.arr[:] = self.arr_backup
            self.info(f"self.arr {self.arr}")


if __name__ == '__main__':
    arr = [int(v) for v in Generator(max_val=100000).do()]
    arr2 = deepcopy(arr)
    print(arr)
    arr_hex = [(v, hex(v)) for v in arr]
    print(arr_hex)
    Radix(arr).sort()
    Profile().print_and_reset()
    
    Radix(arr2, n_bits=7).sort()
    print(arr)
    print(arr2)
    print(arr == arr2)
